Advanced Graph Theory and Combinatorics by Rigo Michel;

Author:Rigo, Michel; [Rigo, Michel]
Language: eng
Format: epub
Publisher: John Wiley & Sons, Incorporated
Published: 2016-11-30T00:00:00+00:00

7.2. A digression: isomorphisms and labeled vertices

In this book, we have not much discussed infinite graphs. Here, we have an opportunity to discuss isomorphisms occurring in infinite trees and make a link with regular languages.

As in remark 7.3, homomorphisms or isomomorphisms can be extended to graphs with labeled vertices. Assume that G (respectively, H) is a digraph with a labeling of the vertices, i.e. a map from V(G) (respectively, V(H)) to a finite set {1, … , k}. In this situation, an isomorphism f between G and H satisfies the same properties as in definition 7.4 and also, for all u ∈ V(G), u and f(u) have the same label.

In formal language theory, we have seen in example 4.11 that we can associate a labeled tree with a language. The set A* of all words over a finite alphabet A is infinite (countable), thus the associated tree has infinitely many vertices. We color vertices in black (respectively, white) if the corresponding word belongs (respectively, does not belong) to the language. In Figure 7.4, we have represented the first four levels of the tree associated with the language a∗b∗ made up of words starting with an arbitrary number of a (possibly 0) followed by an arbitrary number of b. For instance, there is an isomorphism (respecting labels) between the full tree and the tree rooted at the first left child (corresponding to a). Up to isomorphism, the tree contains only three non-isomorphic subtrees: the full tree itself (1), a tree with a black right-most branch (2) and a white tree (3). Consider the subtrees rooted at ε, b and ba.

DEFINITION 7.10.– A language is regular if the associated colored tree has finitely many non-isomorphic subtrees.

This language a∗b∗ is accepted by what is called a deterministic finite automaton (DFA). Such a computational model, as depicted in Figure 7.5, is used to accept/reject in linear time words given as input. The machine reads the letters of the input one by one, from left to right. Starting from the initial state marked by an incoming arrow, the state is updated when reading a letter (we follow transitions in the graph). Accepted states are marked with outgoing arrows. The tree non-isomorphic subtrees correspond to the three states (vertices) of the DFA depicted in Figure 7.5.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.